//组合总和
class Solution {
public:
    vector<vector<int>> ans;
    vector<int> v;
    int num = 0;
    void dfs(vector<int>& candidates,int start,const int& target)
    {
        for(int i = start;i < candidates.size();++i)
        {
            if(num + candidates[i] > target) //剪枝 及时止损
            {
                return;
            }
            if(num + candidates[i] == target) //剪枝
            {
                v.push_back(candidates[i]);
                ans.push_back(v);
                v.pop_back();
                return;
            }
            num += candidates[i];
            v.push_back(candidates[i]);
            dfs(candidates,i,target);  //剪枝 使用i而不是start，防止重复组合
            num -= candidates[i];
            v.pop_back();
        }
        return;
    }
    // void dfs(vector<int>& candidates,int start,const int& target)
    // {
    //     for(int i = start;i < candidates.size();++i)
    //     {
    //         if(num > target)
    //         {
    //             return;
    //         }
    //         if(num == target)
    //         {
    //             ans.push_back(v);
    //             return;
    //         }
    //         num += candidates[i];
    //         v.push_back(candidates[i]);
    //         dfs(candidates,i,target); //剪枝 使用i而不是start，防止重复组合
    //         num -= candidates[i];
    //         v.pop_back();
    //     }
    //     return;
    // }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        std::sort(candidates.begin(),candidates.end(),std::less<int>());
        dfs(candidates,0,target);
        return ans;
    }
};

//滑动窗口最大值
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> q; //记录元素值及其对应的下标
        for(int i = 0;i < k;++i)
        {
            q.push({nums[i],i});
        }
        vector<int> ans{(q.top()).first};
        for(int i = k;i < nums.size();++i)
        {
            q.emplace(nums[i],i);
            while(i - q.top().second + 1 > k)
            {
                q.pop();
            }
            ans.push_back(q.top().first);
        }
        return ans;
    }
};